package leetcode.weekly.week298;

import leetcode.helper.H;

//Solution3Test
public class Solution3 {

	// Solution3Test
	public int longestSubsequence(String s, int k) {
		char[] cs = s.toCharArray();
		char[] ks = Integer.toBinaryString(k).toCharArray();
		if (cs.length < ks.length) {
			return cs.length;
		}
		int cnt = 0;
		int ans = Integer.MIN_VALUE;
		for (int i = 0; i < cs.length; i++) {
			int len1 = this.check(cs, ks, i);
			ans = Math.max(ans, len1 + cnt);
			if (cs[i] == '0') {
				cnt++;
			}
		}
		int ans1 = Integer.MIN_VALUE;
		if (cs.length >= ks.length) {
			ans1 = ks.length - 1;
		}
		return Math.max(ans, ans1);
	}

	private int check(char[] cs, char[] ks, int start) {
		int ans = 0;
		for (int i = start, j = 0; i < cs.length && j < ks.length; i++, j++) {
			if (cs[i] != ks[j]) {
				if (cs[i] < ks[j]) {
					return Math.min(ks.length, cs.length - start);
				} else {
					return ans;
				}
			}
			ans++;
		}
		return ans;
	}

}
